"""
    这道题目的详细解答已经放在课堂的 issues 中了，
    链接 ：https://gitee.com/douma_edu/douma_algo_training_camp/issues/I4A27R
"""
"""
一个正整数数组 arr, 数组满足 0 <= arr[i] <= 9
挑出任意个数，组成一个最大数，并且这个数能被 3 整除，
并以字符串的形式返回
"""
def max_num(arr):
    if len(arr) == 0:
        return ""

    # 记录 arr 中模 3 余数为 1 的最小的数
    min_num_mod_one = 1000000
    # 记录 arr 中模 3 余数为 1 的第二小的数
    second_num_num_mod_one = 1000000
    # 记录 arr 中模 3 余数为 2 的最小的数
    min_num_mod_two = 1000000
    # 记录 arr 中模 3 余数为 2 的第二小的数
    second_num_num_mod_two = 1000000

    total_sum = 0
    # 统计每个元素出现的次数，也用于维护减去的数，以及降序排列
    cnt = [0] * 10
    for num in arr:
        total_sum += num
        cnt[num] += 1

        # 维护 arr 中模 3 余 1 的最小数和第二小数
        if num % 3 == 1:
            if num < min_num_mod_one:
                second_num_num_mod_one = min_num_mod_one
                min_num_mod_one = num
            elif num < second_num_num_mod_one :
                second_num_num_mod_one = num

        # 维护 arr 中模 3 余 2 的最小数和第二小数
        if num % 3 == 2:
            if num < min_num_mod_two:
                second_num_num_mod_two = min_num_mod_two
                min_num_mod_two = num
            elif num < second_num_num_mod_two:
                second_num_num_mod_two = num

    # 总和模 3 余数为 1 时，要减去的数有两种可能，
    # 要么减 1 个余数为 1 的数，要么减 2 个余数为 2 的数。
    if total_sum % 3 == 1:
        if min_num_mod_one <= min_num_mod_two + second_num_num_mod_two:
            cnt[min_num_mod_one] -= 1
        else:
            cnt[min_num_mod_two] -= 1
            cnt[second_num_num_mod_two] -= 1

    # 总和模 3 余数为 2 时，要减去的数有两种可能，
    # 要么减 2 个余数为 1 的数，要么减 1 个余数为 2 的数。
    elif total_sum % 3 == 2:
        if min_num_mod_two <= min_num_mod_one + second_num_num_mod_one:
            cnt[min_num_mod_two] -= 1
        else:
            cnt[min_num_mod_one] -= 1
            cnt[second_num_num_mod_one] -= 1

    res = ""
    # 注意，因为是降序排列，所以从右往左遍历，因为右边是 9
    for num in range(len(cnt) - 1, -1, -1):
        for i in range(cnt[num]):
            res += str(num)

    return res

print()
print(max_num([3, 7, 7, 8, 8, 2, 2]))

# 887322

